1. Field of the Invention
The present invention generally relates to the design and manufacture of integrated circuits, and more particularly to a method of evaluating wire congestion after global routing of an integrated circuit design.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements combined to perform a logic function. Cell types include, for example, core cells, scan cells, input/output (I/O) cells, and memory (storage) cells. Each of the cells of an IC may have one or more pins (connection points for the cell), each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for vertical and/or horizontal routing: the polysilicon layer, and the metal-1, metal-2, and metal-3 layers.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins, including information about the various components such as transistors, resistors and capacitors. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The process of converting the specifications of an electrical circuit into such a layout is called the physical design.
Due to the large number of components and the details required by the fabrication process for very large scale integrated (VLSI) devices, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer-aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance. Several different programming languages have been created for electronic design automation (EDA), including Verilog, VHDL and TDML. A typical EDA system receives one or more high level behavioral descriptions of an IC device, and translates this high level design language description into netlists of various levels of abstraction.
Physical synthesis is prominent in the automated design of integrated circuits such as high performance processors and application specific integrated circuits (ASICs). Physical synthesis is the process of concurrently optimizing placement, timing, power consumption, crosstalk effects and the like in an integrated circuit design. This comprehensive approach helps to eliminate iterations between circuit analysis and place-and-route. Physical synthesis has the ability to repower gates (changing their sizes), insert repeaters (buffers or inverters), clone gates or other combinational logic, etc., so the area of logic in the design remains fluid. However, physical synthesis can take days to complete.
Routability is a key factor when performing circuit floorplanning or trying to close on timing via physical synthesis. A designer can expend considerable effort trying to get the design into a good state in terms of timing and signal integrity, only to subsequently find that it is unroutable. Ideally, the designer should be able to invoke a snapshot routability analysis that allows him or her to understand the routability issues involved from making floorplanning or optimization decisions.
Routing is typically performed in two stages known as global routing and detailed routing. In global routing, the circuit design area is partitioned into a grid of rectangles referred to variously as bins, buckets, global cells (g-cells), or tiles (referred to hereafter as tiles). Each of the boundaries between adjacent tiles is a global edge, and each global edge has wiring tracks used in assigning global interconnections, that is, connections between tiles without consideration of connections or pins inside a tile. Wiring congestion at a given edge is defined as the routing demand divided by the available track capacity. FIG. 1A illustrates an example of two adjacent tiles A and B having a common vertical edge (a vertical edge measures horizontal congestion, and a horizontal edge measures vertical congestion). In this example, there are five possible wiring tracks, and two of those tracks have been assigned connection wires, while a third is designated as a blockage. The resulting edge congestion is accordingly 3/5=60%.
Designers wanting to quantify overall congestion of a globally routed integrated circuit design have devised a set of routing metrics which are based on the congestion of all nets in the design. Net congestion is in turn based on the maximum congestion of global edges which are intersected by a net. FIG. 1B shows a simplified example of a globally routed design 2 having a net 4 with a source 6 and a sink 8. The net is L-shaped, and passes across three vertical edges and two horizontal edges whose edge congestion values are 0.5, 0.6, 0.9, 0.2, and 0.3, respectively. The congestion of net 4 is accordingly 90%. One common metric according to this scheme is the number of overflow nets, defined as the number of nets having a congestion greater than 100%. Similar metrics may use a different percentage, e.g., number of nets greater than 90% congested, or number of nets greater than 80% congested. Another common metric takes an average (mean) of the top 20% worst nets, i.e., the 20% of nets having the worst net congestion. In one example, a first design (Design A) might have an average worst 20% nets value of 89.1%, and an overflow (>100%) value of 9,532, while a second design (Design B) might have an average worst 20% nets value of 83.5%, and an overflow (>100%) value of 532. In such a case, Design B would be deemed preferable because of the lower average 20% and overflow values.
Designers can also use edge congestion values to generate graphic images for a snapshot congestion analysis. A congestion map can be generated by assigning different colors to different congestion values, e.g., blue for 0 to 70%, green for 70% to 80%, yellow for 80% to 90%, red for 90% to 100%, and white over 100%. Such congestion maps can be used for visual inspection to manually identify hotspots in the design.